#proevolytx@gmail.com
#2012/9/16

class StringStream:
    def __init__(s, string):
        s.string = string
        s.index = 0
        
    def Peek(s, length = 1):
        if s.index < len(s.string):
            return s.string[s.index : s.index + length]
        else:
            return None
        
    def Next(s, length = 1):
        if s.index < len(s.string):
            s.index += length

class FileStream(StringStream):
    def __init__(s, path):
        try:
            f = open(path, "rb")
            lines = "".join(f.readlines())
            f.close()
        except:
            raise Exception("Unable to open file: " + path)
        StringStream.__init__(s, lines)

# output format
# {type:none}
# {type:keyword, word:if/while/print}
# {type:word, word}
# {type:num, num}
# {type:symbol, symbol}
class Lexer:
    symbols = ["+", "-", "*", "/", "==", "!=", "<=", "<", ">=", ">", "=",
               "(", ")", "{", "}", ";"]
    
    keywords = ["if", "while", "print"]
    
    def __init__(s, stream):
        s.stream = stream
        s.Next()

    def Peek(s):
        return s.next

    def Next(s):
        s.next = s._ScanNext()
        
    def _ScanNext(s):
        while s.stream.Peek() and s.stream.Peek().isspace():
            s.stream.Next()
        if not s.stream.Peek():
            return {"type":"none"}

        ch = s.stream.Peek()
        if ch.isalpha():
            word = ""
            while s.stream.Peek() and s.stream.Peek().isalnum():
                word += s.stream.Peek()
                s.stream.Next()
            tokenType = "word"
            if word in s.keywords:
                tokenType = "keyword"
            return {
                "type" : tokenType,
                "word" : word,
                }
        elif ch.isdigit():
            num = 0
            while s.stream.Peek() and s.stream.Peek().isdigit():
                num = num * 10 + int(s.stream.Peek())
                s.stream.Next()
            return {
                "type" : "num",
                "num" : num,
                }
        else:
            for sym in s.symbols:
                if s.stream.Peek(len(sym)) == sym:
                    s.stream.Next(len(sym))
                    return {
                        "type" : "symbol",
                        "symbol" : sym,
                        }
            raise Exception("Unrecognizable character: " + ch)

        raise Exception("Impossible to reach here")

# output format
# {type:stmts, left, right}
# {type:keyword, word:if, expr, stmt}
# {type:keyword, word:while, expr, stmt}
# {type:keyword, word:print, expr}
# {type:symbol, symbol, left, right, lvalue}
# {type:word, word}
# {type:num, num}
class Parser:
    operators = [(["="], "R", True),
                 (["==", "!="], "L", False),
                 (["<", ">", "<=", ">="], "L", False),
                 (["+", "-"], "L", False),
                 (["*", "/"], "L", False)]
    
    def __init__(s, lexer):
        s.lexer = lexer

    def Match(s, token):
        p = s.lexer.Peek()
        for key in token:
            if (key not in p) or (p[key] != token[key]):
                raise Exception(str(token) + " expected, but " +
                                str(p) + "instead")
        s.lexer.Next()

    def Program(s):
        return s.Stmts()

    def Block(s):
        s.Match({"type":"symbol", "symbol":"{"})
        stmts = s.Stmts()
        s.Match({"type":"symbol", "symbol":"}"})
        return stmts

    def Stmts(s):
        stmts = []
        t = s.lexer.Peek()
        while t["type"] != "none" and \
              not (t["type"] == "symbol" and t["symbol"] == "}"):
            stmt = s.Stmt()
            stmts.append(stmt)
            t = s.lexer.Peek()
        stmts.reverse()
        while len(stmts) > 1:
            left = stmts[-1]
            right = stmts[-2]
            stmts[-2] = {"type":"stmts", "left":left, "right":right}
            del stmts[-1]
        if len(stmts) == 0:
            return {"type":"none"}
        return stmts[0]

    def Stmt(s):
        t = s.lexer.Peek()
        if t["type"] == "keyword" and t["word"] == "if":
            s.lexer.Next()
            s.Match({"type":"symbol", "symbol":"("})
            t["expr"] = s.Expr()
            s.Match({"type":"symbol", "symbol":")"})
            t["stmt"] = s.Stmt()
            return t
        
        elif t["type"] == "keyword" and t["word"] == "while":
            s.lexer.Next()
            s.Match({"type":"symbol", "symbol":"("})
            t["expr"] = s.Expr()
            s.Match({"type":"symbol", "symbol":")"})
            t["stmt"] = s.Stmt()
            return t

        elif t["type"] == "keyword" and t["word"] == "print":
            s.lexer.Next()
            s.Match({"type":"symbol", "symbol":"("})
            t["expr"] = s.Expr()
            s.Match({"type":"symbol", "symbol":")"})
            s.Match({"type":"symbol", "symbol":";"})
            return t

        elif t["type"] == "symbol" and t["symbol"] == "{":
            return s.Block()

        else:
            expr = s.Expr()
            s.Match({"type":"symbol", "symbol":";"})
            return expr

    def Expr(s, piority = 0):
        if piority >= len(s.operators):
            return s.Factor()
        
        terms, ops = [], []
        terms.append(s.Expr(piority + 1))
        while True:
            t = s.lexer.Peek()
            if t["type"] == "symbol" and \
               t["symbol"] in s.operators[piority][0]:
                ops.append(t)
                s.lexer.Next()
                terms.append(s.Expr(piority + 1))
            else:
                break
                
        if s.operators[piority][1] == "L":
            terms.reverse()
            ops.reverse()

        while ops:
            left = terms[-1]
            right = terms[-2]
            if s.operators[piority][1] == "R":
                left, right = right, left
            op = ops[-1]
            op["lvalue"] = s.operators[piority][2]
            op["left"] = left
            op["right"] = right
            terms[-2] = op
            del terms[-1]
            del ops[-1]

        assert len(terms) == 1
        return terms[0]

    def Factor(s):
        t = s.lexer.Peek()
        if t["type"] in ["word", "num"]:
            s.lexer.Next()
            return t
        elif t["type"] == "symbol" and t["symbol"] == "(":
            s.Match({"type":"symbol", "symbol":"("})
            expr = s.Expr()
            s.Match({"type":"symbol", "symbol":")"})
            return expr

# output format
# {type:declare, name}
# {type:label, name}
# {type:assign, target, source}
# {type:calc, target, left, right, operator}
# {type:print, target}
# {type:ifnot, target}
class CodeGenerator:
    def GenCode(s, root):
        s.varIndex = 0
        s.lblIndex = 0
        s.symbols = {}
        s.codes = []
        s.GenCodeRec(root)
        return s.codes

    def GenCodeRec(s, root):
        if root["type"] == "none":
            return
        if root["type"] == "num":
            return (root["num"], False)
        if root["type"] == "word":
            if root["word"] not in s.symbols:
                s.symbols[root["word"]] = True
                s.codes.append({"type":"declare",
                                "name":root["word"]})
            return (root["word"], True)
        if root["type"] == "symbol":
            t1 = s.GenCodeRec(root["left"])
            t2 = s.GenCodeRec(root["right"])
            if root["symbol"] == "=":
                if root["lvalue"] and not t1[1]:
                    raise Exception("LValue required before assignment")
                code = {"type":"assign",
                        "target":t1[0],
                        "source":t2[0]}
                tr = t1[0]
            else:
                tr = s.NextVar()
                code = {"type":"calc",
                        "target":tr,
                        "left":t1[0],
                        "right":t2[0],
                        "operator":root["symbol"]}
            s.codes.append(code)
            return (tr, False)
        elif root["type"] == "keyword" and root["word"] == "print":
            t = s.GenCodeRec(root["expr"])
            code = {"type":"print", "target":t[0]}
            s.codes.append(code)
        elif root["type"] == "keyword" and root["word"] == "if":
            expr = s.GenCodeRec(root["expr"])
            jmp = {"type":"ifnot", "target":expr[0]}
            s.codes.append(jmp)
            s.GenCodeRec(root["stmt"])
            lbl = s.NextLbl()
            jmp["goto"] = lbl
        elif root["type"] == "keyword" and root["word"] == "while":
            lbl1 = s.NextLbl()
            expr = s.GenCodeRec(root["expr"])
            jmp1 = {"type":"ifnot", "target":expr[0]}
            s.codes.append(jmp1)
            s.GenCodeRec(root["stmt"])
            jmp2 = {"type":"ifnot", "target":0, "goto":lbl1}
            s.codes.append(jmp2)
            lbl2 = s.NextLbl()
            jmp1["goto"] = lbl2
        elif root["type"] == "stmts":
            s.GenCodeRec(root["left"])
            s.GenCodeRec(root["right"])
        
    def NextVar(s):
        result = "_t" + str(s.varIndex)
        s.varIndex += 1
        s.codes.append({"type":"declare", "name":result})
        return result

    def NextLbl(s):
        result = "_L" + str(s.lblIndex)
        s.lblIndex += 1
        s.codes.append({"type":"label", "name":result})
        return result

class IntermediateMachine:
    def Run(s, codes):
        s.codes = codes
        s.vars = {}
        s.pc = 0

        s.lbls = {}
        for i, c in enumerate(s.codes):
            if c["type"] == "label":
                s.lbls[c["name"]] = i

        while True:
            if s.pc >= len(s.codes):
                break
            c = s.codes[s.pc]
            if c["type"] == "declare":
                if c["name"] not in s.vars:
                    s.vars[c["name"]] = 0
                s.pc += 1
            elif c["type"] == "ifnot":
                if s.GetValue(c["target"]) == 0:
                    s.pc = s.lbls[c["goto"]]
                else:
                    s.pc += 1
            elif c["type"] == "print":
                print s.GetValue(c["target"])
                s.pc += 1
            elif c["type"] == "assign":
                s.vars[c["target"]] = s.GetValue(c["source"])
                s.pc += 1
            elif c["type"] == "calc":
                value = 0
                ex = "value = int(" + str(s.GetValue(c["left"])) + " " + \
                     c["operator"] + " " + str(s.GetValue(c["right"])) + ")"
                exec(ex)
                s.vars[c["target"]] = value
                s.pc += 1
            elif c["type"] == "label":
                s.pc += 1
            else:
                raise Exception("Invalide intermediate code")
                
    def GetValue(s, value):
        if type(value) is str:
            return s.vars[value]
        else:
            return value

def PrintTree(root, indent = ""):
    if root["type"] == "symbol":
        print indent + "operator " + root["symbol"]
        print indent + "left"
        PrintTree(root["left"], indent + "  ")
        print indent + "right"
        PrintTree(root["right"], indent + "  ")
    elif root["type"] == "keyword" and root["word"] in ["if", "while"]:
        print indent + root["word"]
        print indent + "expr"
        PrintTree(root["expr"], indent + "  ")
        print indent + "stmt"
        PrintTree(root["stmt"], indent + "  ")
    elif root["type"] == "keyword" and root["word"] == "print":
        print indent + "print"
        print indent + "expr"
        PrintTree(root["expr"], indent + "  ")
    elif root["type"] == "stmts":
        PrintTree(root["left"], indent)
        PrintTree(root["right"], indent)
    else:
        print indent + str(root)

def PrintIntermediate(codes):
    for c in codes:
        if c["type"] == "calc":
            print c["target"] + " = " + \
                  str(c["left"]) + " " + c["operator"] + " " + str(c["right"])
        elif c["type"] == "assign":
            print c["target"] + " = " + str(c["source"])
        elif c["type"] == "declare":
            pass
        elif c["type"] == "print":
            print "print " + str(c["target"])
        elif c["type"] == "ifnot":
            print "ifnot " + str(c["target"]) + " goto " + c["goto"]
        elif c["type"] == "label":
            print c["name"] + ":"
        else:
            raise Exception("Invalide intermediate code")
    
if __name__ == "__main__":
    stream = FileStream("script.txt")
    lexer = Lexer(stream)
    parser = Parser(lexer)
    tree = parser.Program()
    print "\n*** SYNTAX ANALYSING TREE ***\n"
    PrintTree(tree)
    codes = CodeGenerator().GenCode(tree)
    print "\n*** INTERMEDIATE CODE ***\n"
    PrintIntermediate(codes)
    print "\n*** EXECUTION RESULTS BY INTERMEDIATE MACHINE ***\n"
    machine = IntermediateMachine()
    machine.Run(codes)
    print "\n*** ALL DONE ***\n"
